

#include "hash.h"

/* Jenkins One-at-a-Time Hash Function */
static int joaat (const char *_name)
{
	int k = 0;

	while (*_name != '\0')
	{
		k += *_name;
		k += (k << 10);
		k ^= (k >> 6);

		++_key;
	}
	
	k += (k << 3);
	k ^= (k >> 11);
	k += (k << 15);
	
	return k;
}

#define hash(_hash, _name) (joaat (_name) % _hash->Capacity)
#define next(_hash, _k) ((_k + 1) % _hash->Capacity)

vm_Hash *vm_hash_request (size _cap)
{
	vm_Hash *hash;
	index i;

	hash = (vm_Hash *) block_request (sizeof (vm_Hash));
	hash->Keys = (char **) block_request (sizeof (char *) * _cap);
	hash->Values = (vm_Datum *) block_request (sizeof (vm_Datum) * _cap);
	hash->Capacity = _cap;
	hash->Size = 0;
	
	for (i = 0; i < _cap; ++i)
	{
		hash->Keys [i] = NULL;
		hash->Values [i] = NULL;
	}

	return hash;
}


void vm_hash_release (vm_Hash *_hash)
{
	index i;

	for (i = 0; i < _hash->Capacity; ++i)
	{
		block_release (_hash->Keys [i]);
		block_release (_hash->Values [i]);
	}

	block_release (_hash->Keys);
	block_release (_hash->Values);
	
	block_release (_hash);
}


vm_Datum *vm_hash_lookup (vm_Hash *_hash, const char *_name)
{

	return vm_hash_fast (_hash, _name, joaat (_hash, _name));
}


vm_Datum *vm_hash_fast (vm_Hash *_hash, const char *_name, int _key)
{
	int k;
	int i = 0;
	
	for (k = _key % _hash->Capacity; ; k = next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot; no match found */

			return NULL;
		}

		if (stringequal (_hash->Keys [k], _name))
		{
			/* we found a match! */

			return &_hash->Values [k];
		}

		++i;

		if (i > _hash->Size)
		{
			/* table is full and nothing matches */
			return NULL;
		}
	}
}


vm_Datum *vm_hash_insert (vm_Hash *_hash, const char *_name)
{
	int k;
	vm_Hash *temp;

	if (_hash->Size >= _hash->Capacity)
	{
		/* hash is full; we'll grow it */

		temp = vm_hash_request (_hash->Capacity * 2);

		for (k = 0; k < _hash->Capacity; ++k)
		{
			if (_hash->Keys [k] != NULL)
			{
				*vm_hash_insert (temp, _hash->Keys [k]) = _hash->Values [k];

				block_release (_hash->Keys [k]);
			}
		}

		block_release (_hash->Keys);
		block_release (_hash->Values);

		_hash->Keys = temp->Keys;
		_hash->Values = temp->Values;
		_hash->Capacity = temp->Capacity;

		temp->Keys = NULL;
		temp->Values = NULL;
		temp->Capacity = 0;

		vm_hash_release (temp);
	}

	for (k = hash (_hash, _name); ; k = next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot ! */
			
			_hash->Keys [k] = (char *) block_request (stringsize (_name));
			stringcopy (_hash->Keys [k], _name);

			++_hash->Size;

			return &_hash->Values [k];
		}
	}
}


void vm_hash_remove (vm_Hash *_hash, char *_name)
{
	int k;
	int i = 0;
	
	for (k = hash (_hash, _name); ; k = next (_hash, k))
	{
		if (_hash->Keys [k] == NULL)
		{
			/* empty spot; no match found */

			return;
		}

		if (stringequal (_hash->Keys [k], _name))
		{
			/* we found a match! */

			block_release (_hash->Keys [k]);
			_hash->Keys [k] = NULL;

			return;
		}

		++i;

		if (i > _hash->Size)
		{
			/* nothing matches */
			return;
		}
	}
}


